/**
  * Author: Mei
  * Date: 2020-12-13 15:11
  * Description: 红黑树
  */
#include "../../head.h"

using namespace std;

int main() {
    /**
     * 红黑树的应用
     *  红黑树 并不追求“完全平衡 ”——它只要求部分地达到平衡要求，降低了对旋转的要求，
     *          从而提高了性能。
     * 红黑树并不适应所有应用树的领域。如果数据基本上是静态的，那么让他们待在他们能够插入，
     * 并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的，例如，做一个哈希表，
     * 性能可能会更好一些。
     * 应用：
     *  需要使用动态规则的防火墙系统，使用红黑树而不是散列表被实践证明具有更好的伸缩性。
     *  广泛应用于C++的STL中，map和set底层都是用红黑树实现的
     *  只需要保证左右子树中的黑色节点数量一致即可。这是赤裸裸的走捷径啊
     *  从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
     */

    _Rb_tree<int, int, _Identity<int> ,less<int>> itree;
    cout << itree.empty() << endl; //为空返回1
    cout << itree.size() << endl;
    itree._M_insert_unique(3);
    itree._M_insert_unique(5);
    itree._M_insert_unique(7);
    itree._M_insert_unique(4);
    itree._M_insert_unique(4);
    cout << itree.empty() << endl;
    cout << itree.size() << endl;
    cout << itree.count(4) << endl;

    vector<int> vec{1,2};
    return 0;
}